#include "main/utils.h"
using namespace std;

int partition(vector<int>& nums, int begin, int end) {
  int i = begin - 1;
  for (int j = begin; j < end; j++) {
    if (nums[j] < nums[end]) {
      ++i;
      swap(nums, i, j);
    }
  }
  ++i;
  swap(nums, i, end);
  return i;
}

void quick_sort(vector<int>& nums, int begin, int end) {
  if (begin >= end) {
    return;
  }
  int prive = partition(nums, begin, end);
  quick_sort(nums, begin, prive - 1);
  quick_sort(nums, prive + 1, end);
}

void quickSort(vector<int>& nums) {
  quick_sort(nums, 0, nums.size() - 1);
}

int main() {
  vector<int> nums = {4, 6, 2, 7, 1, 9, 0, 4};
  quickSort(nums);
  printVec("quick_sort", nums);

  return 0;
}
